Міністерство Освіти України Національний університет «Львівська політехніка» Методичні вказівки До лабораторної роботи № 10 На тему: «Методи пошуку. Бінарний пошук» з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» ЗАТВЕРДЖЕНО на засіданні кафедри програмного забезпечення протокол № від 2008 року місто Львів 2008 рік Методичні вказівки до лабораторної роботи з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» Укладачі: Семчишин Ю. Б. Коротєєва Т. О. Вовчак І. Г. Відповідальний за випуск: Рецензенти: Тема роботи: Ознайомлення із методами пошуку. Алгоритм бінарного пошуку. Мета роботи: Вивчити та дослідити методи пошуку, як один із методів обробки даних. Ознайомитись із методом бінарного пошуку. Виконати лабораторну роботу використавши здобуті знання з методів пошуку, зокрема методу бінарного пошуку. ТЕОРЕТИЧНІ ВІДОМОСТІ Двійковий пошук (англ. Binary Search) — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини, залежно від результату порівняння. Двійковий пошук суттєво швидший за лінійний, відносно простий в реалізації і загальновживаний. Обчислювальна складність алгоритму становить О(log2N). РЕКОМЕНДОВАНІ ДЖЕРЕЛА http://www.wikipedia.org/. Donald Ervin Knuth «The Art of Computer Programming». 2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати бінарний пошук. Використовувати мову програмування C/C++. Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи. 3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ Отримати індивідуальне завдання у викладача; Уточнити завдання (можливі різні трактування завдання); Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу (алгоритму) на даній лабораторній роботі; Протестувати на наявність логічних помилок програми; Оформити звіт відповідно до стандарту; Захистити виконану роботу. 4. КОНТРОЛЬНІ ПИТАННЯ Які ви знаєте методи пошуку? Який метод пошуку був розглянений на даній лабораторній роботі? Від чого прямо – залежним являється швидкість пошуку? Опишіть характеристики даного методу. Порівняєте даний метод із іншими методами пошуку вам відомими. Наскільки являється ефективним даний метод пошуку? Чи використовують даний метод на практиці, і наскільки часто? Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах? Чим оригінальним виділяється даний метод від інших?